//503.下一个更大元素Ⅱ
//https://leetcode.cn/problems/next-greater-element-ii
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        //两次遍历数组 防止首位数字被漏掉的情况
        // 1 2 1 1 2 1
        int n = nums.size();
        vector<int> ret(n,-1);
        stack<int> st;

        for(int i = 0;i<2*n;++i)
        {
            //两次遍历数组
            int num = nums[i%n];
            //栈是一个单调递减栈 存储比自己小的数 也就是要找比自己大的数
            //里面最大的数寻找不到比自己大的数会留在栈中
            //而数组前面比较大的数在二次遍历时会得知比自己大的数
            while(!st.empty() && nums[st.top()] < num)
            {
                //当num比自己大时 栈中的数可以更新比自己大的数
                //因为是单调栈 所以num肯定比栈中的下标数字要大
                ret[st.top()] = num;
                st.pop();
            }
            if(i < n) st.push(i);
        }
        return ret;
    }
};